package main

import (
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
执行用时：8 ms, 在所有 Go 提交中击败了91.84%的用户
内存消耗：6 MB, 在所有 Go 提交中击败了25.88%的用户
 */
//func mergeKLists(lists []*ListNode) *ListNode {
//
//	if len(lists) == 0 { return nil }
//
//	for step := 1; step < len(lists); step *= 2 {
//		for i := 0; i + step < len(lists); i += step + step {
//			lists[i] = merge(lists[i], lists[i + step])
//		}
//	}
//	return lists[0]
//}

/**
执行用时：8 ms, 在所有 Go 提交中击败了91.84%的用户
内存消耗：6 MB, 在所有 Go 提交中击败了29.23%的用户
 */
func mergeKLists(lists []*ListNode) *ListNode {

	lg := len(lists)
	if lg < 1 { return nil }
	if lg == 1 { return lists[0] }

	mid := lg / 2
	left, right := mergeKLists(lists[:mid]), mergeKLists(lists[mid:])
	return merge(left, right)
}

func merge(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil { return l2 }
	if l2 == nil { return l1}

	if l1.Val <= l2.Val {
		l1.Next = merge(l1.Next, l2)
		return l1
	} else {
		l2.Next = merge(l1, l2.Next)
		return l2
	}
}

func main() {
	fmt.Println("Hello World!")
}
